This invention relates generally to computers and computation equipment and more particularly to devices and methods for accomplishing high speed mathematical operations.
As is known, one of the primary building blocks of any digital computer or computing means is the ALU circuit. That circuit employs a binary adder composed of plural gates forming a half-adder circuit and at least one full-adder cirucit. As is known, a conventional half-adder circuit is a logic circuit for adding a pair of single bits and most commonly consists of a two input EXCLUSIVE OR gate and a two input AND gate. The gates are connected so that one bit is provided to one input of each gate while the other bit is provided to the other input of each gate. The output of the EXCLUSIVE OR gate is the signal equal to the "sum" of the two bits without carry while the output of the AND gate is the "carry" bit. Since a half-adder can only add two bits at a time a full adder is required to add three or more bits. Thus, a full-adder for three bits consists of a three input EXCLUSIVE OR gate, each of whose inputs is provided with a respective bit to be added. The full-adder also includes three, two input AND gates. The inputs of one AND gate is provided with the first and second bits to be added, while the inputs of the second AND gate are provided with the first and third bits to be added and the inputs of the third AND gate are provided with the second and third bits to be added. The output of the three AND gates are provided as respective inputs to an OR gate. In such an arrangement the EXCLUSIVE OR gate provides the "sum" bit while the OR gate provides the "carry" bit.
In order to form a binary adder circuit to add two multibit binary numbers plural full-adder circuits are connected in cascade with each other and with a half-added. As will be appreciated by those skilled in the art, with such an arrangement, before each successive stage of the binary adders can effect the addition of its bits, the carry bit for the preceding stage must be known (i.e., determined). This factor, (referred to frequently as "carry bit propogation"), renders binary addition and subtraction, a serial process, with the time necessary to complete the mathematical operation being a function of the number of stages in the binary adder. Since multiplication and division are effected as a function of addition/subtraction, carry bit propogation is thus a factor in the speed of operation of circuits for performing those operations also.
In order to overcome the time wastage problems of carry bit propogation, so as to result in faster circuits for performing mathematical functions, various techniques have been disclosed to determine the content of each carry bit prior to the combination (e.g., addition) of the bits producing that carry bit. Such techniques are frequently referred to as carry bit "look-ahead" techniques. An example of a carry bit look-ahead technique is shown in U.S. Pat. No. 3,604,910 (Kearns) and in the following literature: H. Ling, "High Speed Binary Parallel Adder", IEEE Transactions on Electronic Computers, pp. 799-802 (1966); H. Ling, "High Speed Binary Adder", IBM Journal of Research and Development, Vol. 2W5, No. 3, pp. 156-160, May 1981; J. Sklansky, "An Evaluation of Several Two-Summand Binary Adders", IRE Transactions on Electronic Computers, pp. 213-226 (June 1966), and Texas Instruments Incorporated Data Book, p. 393, "Types SN54l82 and SN74l82 Look-Ahead Carry Generators".
While prior art carry bit look-ahead techniques may result in a speed improvement over a conventional circuits, they nevertheless leave much to be desired from the standpoint of simplicity of construction, e.g., require large n-input devices, and effectiveness of operation.